//https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=23291&ru=%2Fpractice%2F29311ff7404d44e0b07077f4201418f5&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13

//重点！！！
//思想：dfs + set容器实现：实现字符串的

#include <string>
#include <vector>
#include <set>

using namespace std;

class Solution {
  public:
    void dfs(int loc, string& s, set<string>& ans) {
        if (loc == s.size() - 1) { //递归边界
            ans.insert(s);//找到一个排序，并且插入
            return ;
        }
        for (int i = loc; i < s.size(); i++) { //假设原来的元素映射到他的下标，那么我们搜索的是下标的全排序
            swap(s[i], s[loc]);
            dfs(loc + 1, s, ans); //进入下一层递归
            swap(s[i], s[loc]); //还原s
        }
    }
    vector<string> Permutation(string str) {
        if (str.empty())return {};
        set<string> ans;//因为题目说str中可能有重复元素，所以需要集合来去重,并且起到从小到大排序作用
        dfs(0, str, ans); //开始搜索字符串
        return vector<string>(ans.begin(), ans.end()); //vector迭代器拷贝初始化，只需要元素的类型一样即可，跟容器无关
    }
};